#include "Graph.h"

// 使用Floyd算法计算所有节点对之间的最短路径
void FloydShortestPaths(Graph* g, int nodeCount)
{
    int dist[nodeCount][nodeCount] = {0};
    // 初始化距离矩阵
    for (int i = 0; i < nodeCount; ++i)
    {
        for (int j = 0; j < nodeCount; ++j) //初始各点间距离为无穷大
        {
            dist[i][j] = INT_MAX;
        }
        for (int j = 0; j < g->nodeSet[i]->nexts.size(); ++j)//设置实际边距离
        {
            auto neib = g->nodeSet[i]->nexts[j];
            auto edge = g->nodeSet[i]->edges[j];
            if(dist[i][neib->value] > edge->weight) //防止两点间有多条长度不一的路径
            {
                dist[i][neib->value] = edge->weight;
            }
        }
        dist[i][i] = 0; // 自己到自己的距离为0
    }
    // 更新距离矩阵
    for (int k = 0; k < nodeCount; ++k) //中继点
    {
        for (int i = 0; i < nodeCount; ++i) //起点
        {
            for (int j = 0; j < nodeCount; ++j) //终点
            {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][j] > dist[i][k] + dist[k][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    //打印最短路径图
    for (int i = 1; i < nodeCount; ++i)
    {
        for (int j = 1; j < nodeCount; ++j)
        {
            printf("%d ", dist[i][j]);
        }
        printf("\n");
    }
}